package com.zhang.sort;

/**
 * @author ZhangJiXin
 * @Description 计数排序优化版
 * @date 2021/4/25 10:14
 */
public class CountingSort2 extends Sort<Integer>{
    /**
     * 首先找到数组元素中最大值和最小值 新创建的数组长度 = 最大值 - 最小值
     * 通过这种方式可以压缩 新创建的数组长度 查找元素对应的索引 = 元素 - 最小值
     * 首先记录元素出现的次数
     * 然后将每个元素出现的次数 加上 上一个元素的次数 进行统计
     * 最后再创建一个 跟 需要排序的数组长度一样的数组
     * 倒叙遍历 每个元素出现的次数 -1 就是排序后出现的索引
     * 最后将排序好的数组元素 覆盖到 原来的数组
     * 这种优化实现弥补了 ①空间复杂度特别大的情况 ②可以对负数进行排序 ③是稳定排序
     * @Author ZhangJiXin
     * @Date 2021/4/26 8:47
     * @return: void
     */
    @Override
    protected void sort() {
        //找到数组元素中最大值和最小值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]){
                max = array[i];
            }
            if (min > array[i]){
                min = array[i];
            }
        }

        int[] counts = new int[max - min + 1];
        //计算每个元素出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] - min]++;
        }
        //累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        //进行排序
        Integer[] newArray = new Integer[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            int elements = array[i];
            newArray[--counts[elements - min]] = elements;
        }

        //排序好的数组 覆盖原来的数组
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }

    }
}
